# -*- coding: utf-8 -*-

'''
@author: 5822 - Duarte Marques & 5955 - João Rosa
@date: 06 de Junho de 2013
@obs: Trabalho de Estruturas de Dados e Algoritmos
      Docente: Prof. Jasnau Caeiro
'''

import sys
import math

class merge_sort:
	'''
	Classe que contém o algoritmo Merge_Sort.
	'''

	def __init__(self, A):
		'''
		Metodo onde inicializam algumas variaveis para
		serem utilizadas mais tarde.
		Recebe como parameto uma lista "A", .
		'''
		self.A = A

	def merge(self, p, q, r):
		'''
		Metodo que pega na lista dividida em dois e
		faz a troca das posições para ordenar a lista.
		Recebe como parametro:
								"p" - inicio da lista
								"q" - meio da lista
								"r" - fim da lista
		'''
		n1 = q - p + 1
		n2 = r - q 

		L = [0 for x in range(n1+1)]
		R = [0 for x in range(n2+1)]
		
		for i in range(n1):
			L[i] = self.A[p + i]
			pass

		for j in range(n2):
			R[j] = self.A[q + j + 1]
			pass
		
		L[n1] = sys.maxint
		R[n2] = sys.maxint

		i = 0
		j = 0
		for k in xrange(p, r+1):
			if L[i] <= R[j]:
				self.A[k] = L[i]
				i = i + 1
			else:
				self.A[k] = R[j]
				j = j + 1
				pass
			pass

	def merge_sort(self, p, r):
		'''
		Metodo que recebe uma lista, o seu indice inicial e o indice final,
		para em conjunto com o "merge_sort", ordenarem a lista.
		'''
		if p < r:
			q = (p + r)/2
			self.merge_sort(p, q)
			self.merge_sort(q + 1, r)
			self.merge(p, q, r)
		return self.A


# #A = [2,4,5,7,1,2,3,6]
# A = [450,500,550,150,200,250,300,350,400,750,800,600,650,700,1,50,100,850,900,950,1000,1050]
# print A
# print (len(A)-1)/(2)

# g = merge_sort(A)
# #g = merge_sort(A, 0, (len(A)-1)/(2), len(A)-1)
# print g.merge_sort(0, len(A)-1)